# 10. 跳跃游戏 II.py
from typing import List

class Common_Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        jump_counts = [0 for _ in range(n)]
        for i in range(n):
            # 限制防止越界。
            rightmost = min(n, i+nums[i]+1)
            for j in range(i+1, rightmost):
                if jump_counts[j] == 0:
                    jump_counts[j] = jump_counts[i]+1
                else:
                    jump_counts[j] = min(jump_counts[i] + 1, jump_counts[j])
        return jump_counts[n-1]

# 官方最优题解
# 正向查找可到达的最大位置
# 这里没有考虑能不能达到，而是不断统计可达的最大位置，因为题目默认可达。
# 题目可以深化：如果不可达返回-1，可达的话，返回到达的最小jump数。
class Solution:
    def jump(self, nums: List[int]) -> int:
        n, rightmost = len(nums), 0
        # 用bound这个思路很巧妙！
        bound = 0
        ans_steps = 0
        # 为什么是n-1，因为最后一个元素不需要考虑。
        for i in range(n-1):
            if rightmost >= i:
                # 不断遍历寻找当前的jump次数下所能到达的最远位置
                rightmost = max(rightmost, i + nums[i])
                # 找到当前的边界后，就说明需要增加jump的次数
                if i == bound:
                    bound = rightmost
                    ans_steps += 1
        return ans_steps